#ifndef AFBS_H_
#define AFBS_H_

#include <algorithm>
#include <array>
#include <cmath>
#include <queue>
#include <vector>

namespace lxj
{
// Dijkstra算法
// grid[i][j] == 0 代表障碍
// grid[i][j] == 1 代表道路
// 只能走上、下、左、右，不包括斜线方向
// 返回从(startX, startY)到(targetX, targetY)的最短距离
inline int minDistance1(
    std::vector<std::vector<int>>& grid, int startX, int startY, int targetX, int targetY)
{
    constexpr int move[] = {-1, 0, 1, 0, -1};
    if (grid[startX][startY] == 0 || grid[targetX][targetY] == 0) return -1;

    constexpr int                 MAX = ~(1 << 31);
    int                           n   = grid.size();
    int                           m   = grid[0].size();
    std::vector<std::vector<int>> distance(n, std::vector<int>(m, MAX));

    distance[startX][startY] = 1;
    std::vector<std::vector<bool>> visited(n, std::vector<bool>(m, false));

    using node = std::array<int, 3>;
    auto comp  = [](const node& a, const node& b) { return a[2] > b[2]; };
    std::priority_queue<node, std::vector<node>, decltype(comp)> heap(comp);
    heap.push({startX, startY, 1});
    while (!heap.empty()) {
        auto& cur = heap.top();
        int   x   = cur[0];
        int   y   = cur[1];
        heap.pop();
        if (visited[x][y]) continue;
        visited[x][y] = true;
        if (x == targetX && y == targetY) return distance[x][y];
        for (int i = 0, nx, ny; i < 4; i++) {
            nx = x + move[i];
            ny = y + move[i + 1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1 && !visited[nx][ny] &&
                distance[x][y] + 1 < distance[nx][ny]) {
                distance[nx][ny] = distance[x][y] + 1;
                heap.push({nx, ny, distance[x][y] + 1});
            }
        }
    }
    return -1;
}

// A*算法
// grid[i][j] == 0 代表障碍
// grid[i][j] == 1 代表道路
// 只能走上、下、左、右，不包括斜线方向
// 返回从(startX, startY)到(targetX, targetY)的最短距离
inline int minDistance2(
    std::vector<std::vector<int>>& grid, int startX, int startY, int targetX, int targetY)
{
    if (grid[startX][startY] == 0 || grid[targetX][targetY] == 0) return -1;
    constexpr int                 move[] = {-1, 0, 1, 0, -1};
    constexpr int                 MAX    = ~(1 << 31);
    int                           n      = grid.size();
    int                           m      = grid[0].size();
    std::vector<std::vector<int>> distance(n, std::vector<int>(m, MAX));

    distance[startX][startY] = 1;
    std::vector<std::vector<bool>> visited(n, std::vector<bool>(m, false));

    using node = std::array<int, 3>;
    auto comp  = [](const node& a, const node& b) { return a[2] > b[2]; };
    std::priority_queue<node, std::vector<node>, decltype(comp)> heap(comp);

    // 曼哈顿距离
    auto mhtd = [targetX, targetY](int x, int y) {
        return (std::abs(targetX - x) + std::abs(targetY - y));
    };

    // 对角线距离（适合可走斜线的情况）
    auto diagonal = [targetX, targetY](int x, int y) {
        return std::max(std::abs(targetX - x), std::abs(targetY - y));
    };

    // 欧式距离
    auto pythagorean = [targetX, targetY](int x, int y) {
        long long xx = (targetX - x) * (targetX - x);
        long long yy = (targetY - y) * (targetY - y);
        return (int)std::sqrt(xx + yy);
    };

    heap.push({startX, startY, 1 + mhtd(startX, startY)});
    while (!heap.empty()) {
        auto& cur = heap.top();
        int   x   = cur[0];
        int   y   = cur[1];
        heap.pop();
        if (visited[x][y]) continue;
        visited[x][y] = true;
        if (x == targetX && y == targetY) return distance[x][y];
        for (int i = 0, nx, ny; i < 4; i++) {
            nx = x + move[i];
            ny = y + move[i + 1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1 && !visited[nx][ny] &&
                distance[x][y] + 1 < distance[nx][ny]) {
                distance[nx][ny] = distance[x][y] + 1;
                heap.push({nx, ny, distance[x][y] + 1 + mhtd(nx, ny)});
            }
        }
    }
    return -1;
}

// Floyd算法模版（洛谷）
// 测试链接 : https://www.luogu.com.cn/problem/P2910
inline int floyd(int n, std::vector<int>& paths, std::vector<std::vector<int>>& dangers)
{
    constexpr int                 MAX = ~(1 << 31);
    std::vector<std::vector<int>> distance(n, std::vector<int>(n, MAX));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) distance[i][j] = dangers[i][j];
    }

    for (int bridge = 0; bridge < n; bridge++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (distance[i][bridge] != MAX && distance[bridge][j] != MAX &&
                    distance[i][j] > distance[i][bridge] + distance[bridge][j]) {
                    distance[i][j] = distance[i][bridge] + distance[bridge][j];
                }
            }
        }
    }

    int ans = 0;
    for (auto& p : paths) p -= 1;
    for (int i = 1; i < paths.size(); i++) {
        ans += distance[paths[i - 1]][paths[i]];
    }
    return ans;
}

// Bellman-Ford算法应用（不是模版）
// k站中转内最便宜的航班
// 有 n 个城市通过一些航班连接。给你一个数组 flights
// 其中 flights[i] = [fromi, toi, pricei]
// 表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
// 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k
// 站中转的路线 使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。
// 测试链接 : https://leetcode.cn/problems/cheapest-flights-within-k-stops/
inline int findCheapestPrice(int n, std::vector<std::vector<int>>& flights, int src, int dst, int k)
{
    constexpr int    MAX = ~(1 << 31);
    std::vector<int> distance(n, MAX);
    distance[src] = 0;
    for (int i = 0; i <= k; i++) {
        std::vector<int> next(distance);
        for (auto& edge : flights) {
            if (distance[edge[0]] != MAX)
                next[edge[1]] = std::min(next[edge[1]], distance[edge[0]] + edge[2]);
        }
        distance = next;
    }
    return distance[dst] == MAX ? -1 : distance[dst];
}

// Bellman-Ford + SPFA优化模版（洛谷）
// 给定n个点的有向图，请求出图中是否存在从顶点1出发能到达的负环
// 负环的定义是：一条边权之和为负数的回路
// 测试链接 : https://www.luogu.com.cn/problem/P3385
class SPFA {
    inline constexpr static int MAXN         = 2001;
    inline constexpr static int MAXM         = 6001;
    inline static int           head[MAXN]   = {};
    inline static int           to[MAXM]     = {};
    inline static int           weight[MAXM] = {};
    inline static int           next[MAXM]   = {};
    inline static int           cnt          = 0;

    inline static int distance[MAXN]  = {};
    inline static int updateCnt[MAXN] = {};

    inline constexpr static int    MAXQ  = 4000001;
    inline static std::vector<int> queue = std::vector<int>(MAXQ);
    inline static int              l = 0, r = 0;
    inline static bool             enter[MAXN] = {};

    inline void build(int n)
    {
        cnt = 1;
        l = 0, r = 0;
        std::fill(head, head + n + 1, 0);
        std::fill(enter + 1, enter + n + 1, false);
        std::fill(distance + 1, distance + n + 1, ~(1 << 31));
        std::fill(updateCnt, updateCnt + n + 1, 0);
    }

    inline void addEdge(int u, int v, int w)
    {
        next[cnt]   = head[u];
        to[cnt]     = v;
        weight[cnt] = w;
        head[u]     = cnt++;
    }

public:
    inline bool spfa(int n, std::vector<std::array<int, 3>>& edges)
    {
        build(n);
        for (auto& edge : edges) {
            if (edge[2] < 0) {
                addEdge(edge[0], edge[1], edge[2]);
            }
            else {
                addEdge(edge[0], edge[1], edge[2]);
                addEdge(edge[1], edge[0], edge[2]);
            }
        }

        distance[1] = 0;
        updateCnt[1]++;
        queue[r++] = 1;
        enter[1]   = true;
        while (l < r) {
            int u    = queue[l++];
            enter[u] = false;
            for (int ei = head[u], v, w; ei > 0; ei = next[ei]) {
                v = to[ei];
                w = weight[ei];
                if (distance[u] + w < distance[v]) {
                    distance[v] = distance[u] + w;
                    if (!enter[v]) {
                        if (++updateCnt[v] > n - 1) return true;
                        queue[r++] = v;
                        enter[v]   = true;
                    }
                }
            }
        }
        return false;
    }
};
}   // namespace lxj

#endif